package com.adee.nowcoder.huawei;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;

public class T016_HJ16 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String s = in.nextLine();
            String[] arr = s.split(" ");
            int N = Integer.parseInt(arr[0]); // 预算
            int n = Integer.parseInt(arr[1]);
            List<P> list = new ArrayList<>();
            for(int i = 0; i < n; i++) {
                P p = new P(in.nextLine());
                list.add(p);
            }
            for(int i = 0; i < list.size(); i++) {
                P p = list.get(i);
                if(p.isMain != 0) {
                    P mainP = list.get(p.isMain-1);
                    if(mainP.f1 == null) {
                        mainP.f1 = p;
                    } else {
                        mainP.f2 = p;
                    }
                }
            }
            // list中删除附件，只遍历主物品
            Iterator<P> it = list.iterator();
            while(it.hasNext()) {
                if(it.next().isMain != 0) {
                    it.remove();
                }
            }

            // 按01背包方式处理list
            int[][] bp = new int[list.size()][N+1];
            for(int i = 0; i < bp.length; i++) {
                P p = list.get(i);
                for(int j = 1; j < bp[0].length; j++) {

                    if(i == 0) {
                        // 1.只选主物品
                        int sfi = p.v>j ? 0 : p.v*p.w;
                        // 2.主物品+附件
                        int sfi1 = 0;
                        if(p.f1 != null) {
                            sfi1 = p.v+p.f1.v>j ? 0 : p.v*p.w+p.f1.v*p.f1.w;
                        }
                        int sfi2 = 0;
                        if(p.f2 != null) {
                            sfi2 = p.v+p.f2.v>j ? 0 : p.v*p.w+p.f2.v*p.f2.w;
                        }
                        int sfi3 = 0;
                        if(p.f1 != null && p.f2 != null) {
                            sfi3 = p.v+p.f1.v+p.f2.v>j ? 0 : p.v*p.w+p.f1.v*p.f1.w+p.f2.v*p.f2.w;
                        }
                        bp[i][j] = Math.max(Math.max(sfi,sfi1),Math.max(sfi2,sfi3));
                    } else {
                        // sfi 表示 如果选择当前物品i，则最大满意度为多少
                        // 1.只选主物品
                        int sfi = p.v>j ? 0 : p.v*p.w + bp[i-1][j-p.v]; // 当前物品list.get(i)的价格超过了预算，肯定不能选当前物品了
                        // 2.主物品+附件
                        int sfi1 = 0;
                        if(p.f1 != null) {
                            sfi1 = p.v+p.f1.v>j ? 0 : p.v*p.w+p.f1.v*p.f1.w + bp[i-1][j-p.v-p.f1.v];
                        }
                        int sfi2 = 0;
                        if(p.f2 != null) {
                            sfi2 = p.v+p.f2.v>j ? 0 : p.v*p.w+p.f2.v*p.f2.w + bp[i-1][j-p.v-p.f2.v];
                        }
                        int sfi3 = 0;
                        if(p.f1 != null && p.f2 != null) {
                            sfi3 = p.v+p.f1.v+p.f2.v>j ? 0 : p.v*p.w+p.f1.v*p.f1.w+p.f2.v*p.f2.w + bp[i-1][j-p.v-p.f1.v-p.f2.v];
                        }

                        bp[i][j] = Math.max(bp[i-1][j], Math.max(Math.max(sfi,sfi1),Math.max(sfi2,sfi3)));
                    }
                }
            }

            System.out.println(bp[bp.length-1][bp[0].length-1]);

        }


    }


    public static class P {
        public int v;
        public int w;
        public int isMain;
        public P f1;
        public P f2;
        public P(String s) {
            String[] arr = s.split(" ");
            v = Integer.parseInt(arr[0]);
            w = Integer.parseInt(arr[1]);
            isMain = Integer.parseInt(arr[2]);
        }
    }
}
